Ray-tracing is a field of computer graphics techniques that can produce superior, photorealistic digital images. Ray-tracing or ray-casting is a three-dimensional (3-D) rendering technique that determines the location of an object in 3-D and calculates shadows, reflections, and hidden surfaces based on lighting conditions and locations, as well as material characteristics. The visibility of surfaces is determined by tracing rays of light from the viewer's vantage to objects in a scene.
Ray-tracing differs from z-buffer oriented methods by being ray centric, as opposed to primitive centric. Instead of drawing primitives to a screen, rays are cast from a virtual eye, or center of projection, through screen pixels (i.e., a view plane) to find intersecting primitives for those pixels. Each pixel has a color set to that of the primitive at the closest point of intersection. While ray-tracing has existed for quite some time, only recently has research started to make ray-tracing algorithms run in real time. Current applications for ray-tracing include movie and advertising business for precalculated visualizations.
Interactive and real time ray-tracing are closely related areas, but are not quite the same. “Interactive” refers to the ability to compute scenes at real time speeds, without prior knowledge of future frames (e.g., a user may be able to control scene content directly). “Real time” refers to the ability to compute scenes at speeds sufficiently high to convey the perception of motion to the human eye and allowing an algorithm with knowledge of future frames (more of a prescripted movie approach to animation).
Fujimoto, A., Tanaka, T., and Iwata, K., “ARTS: Accelerated Ray-Tracing System”, IEEE CG&A, April 1986, pp. 16–26, and hereby fully incorporated by reference, describe a three-dimensional digital differential analyzer (3DDDA) that seeks to address issues of speed and aliasing in ray-tracing. The 3DDDA is a 3D line generator for traversing a data structure describing a 3D environment to identify the intersections between rays and objects in the image to be generated. The 3DDDA identifies cells pierced by a ray or straight line and generates the coordinates of the cells. One implementation of a 3DDDA is to use two DDAs synchronized to work in mutually perpendicular planes that intersect along a driving axis DA (i.e., a coordinate axis). In each plane, the respective DDA follows the projection of the 3-D line onto that plane. The coordinate corresponding to the driving axis DA of each DDA is unconditionally incremented by one unit, where the slope of the line determines DA. A control term (or error term) for each DDA measured perpendicular to the DA is updated; this is done by subtracting from the control term the slope value and determining if it satisfies a stipulated condition. Both control terms are measured against the same DDA. If the test fails, a unit increment or decrement of the coordinate perpendicular to the DA is performed for the DDA. The control term is corrected by adding the value corresponding to one pixel whenever underflow occurs.
In a variety of applications such as ray-tracing and radiosity, the intersection of a three-dimensional (3D) triangle with a regularly spaced three-dimensional (3D) grid is needed. Those skilled in the art will appreciate a plurality of other applications to which determination of the intersection of a triangle (or other polygonal shape) with a 3D grid may apply. It should be appreciated, however, that, in general and for ray-tracing and radiosity in particular, determination of the intersection of a triangle with a 3D grid is most often encountered for the simple reason that a triangle provides a relatively more simple mathematical construct than other polygons while a surface of any arbitrary shape may be approximated by contiguous triangles. For example, in the field of ray-tracing, this determination is used to computation efficiently determine the intersection of a ray within a set of triangles. Only those triangles that intersect one or more of the volume elements or voxels that a ray intersects need to be considered for intersection with that same ray. A voxel in this context is one individual cell of a three-dimensional (3D), regularly spaced grid.
Given the large number of triangles that are typically needed to describe in detail a three-dimensional scene of some realism, the computational efficiency of the three-dimensional triangle bounding voxelisation process is crucial. In particular, known techniques for determination of geometric shapes such as triangles or their boundaries has required numerous division operations which are particularly computation intensive and require multiple processing cycles as contrasted with addition, subtraction and multiplication which may often be completed in a single processing cycle. Accordingly, extreme processing power is required to perform such techniques at sufficient speed to approach real time or interactive generation of high-quality graphics. While some acceleration of processing can often be achieved using special purpose hardware such as application specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs), possibly in combination with general purpose processors, the number of processing operations required to perform division at sufficient speeds for real time or interactive performance makes such hardware extremely complex and expensive to develop and fabricate.